Quantum algorithm for neighborhood preserving embedding

Neighborhood preserving embedding (NPE) is an important linear dimensionality reduction technique that aims at preserving the local manifold structure. NPE contains three steps, i.e., finding the nearest neighbors of each data point, constructing the weight matrix, and obtaining the transformation matrix. Liang et al. proposed a variational quantum algorithm (VQA) for NPE [Phys. Rev. A 101 032323 (2020)]. The algorithm consists of three quantum sub-algorithms, corresponding to the three steps of NPE, and was expected to have an exponential speedup on the dimensionality n. However, the algorithm has two disadvantages: (i) It is not known how to efficiently obtain the input of the third sub-algorithm from the output of the second one. (ii) Its complexity cannot be rigorously analyzed because the third sub-algorithm in it is a VQA. In this paper, we propose a complete quantum algorithm for NPE, in which we redesign the three sub-algorithms and give a rigorous complexity analysis. It is shown that our algorithm can achieve a polynomial speedup on the number of data points m and an exponential speedup on the dimensionality n under certain conditions over the classical NPE algorithm, and achieve a significant speedup compared to Liang et al.'s algorithm even without considering the complexity of the VQA.     

全局优化问题的一个新的无参数填充函数

求全局最优化问题的填充函数算法被提出以来，参数的选取和调整一直是制约算法有效性的因素。如何在实际的计算过程中选取合适的参数，直接影响和决定了运算速度和效率。因此，构造不含参数的填充函数就显得极为重要。提出一个新的无参数的填充函数，对其理论性质进行了分析，并给出相应的填充函数算法，数值计算验证了算法的有效性。     

Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

This letter studies the problem of minimizing increasing set functions, equivalently, maximizing decreasing set functions, over the base matroid. This setting has received great interest, since it generalizes several applied problems including actuator and sensor placement problems in control, task allocation problems, video summarization, and many others. We study two greedy heuristics, namely, the forward and reverse greedy. We provide two novel performance guarantees for the approximate solutions obtained by them depending on both submodularity ratio and curvature.     

Oscillation and non‐oscillation results for solutions of perturbed half‐linear equations

The purpose of this paper is to describe the oscillatory properties of second‐order Euler‐type half‐linear differential equations with perturbations in both terms. All but one perturbations in each term are considered to be given by finite sums of periodic continuous functions, while coefficients in the last perturbations are considered to be general continuous functions. Since the periodic behavior of the coefficients enables us to solve the oscillation and non‐oscillation of the considered equations, including the so‐called critical case, we determine the oscillatory properties of the equations with the last general perturbations. As the main result, we prove that the studied equations are conditionally oscillatory in the considered very general setting. The novelty of our results is illustrated by many examples, and we give concrete new corollaries as well. Note that the obtained results are new even in the case of linear equations.     

Local linear convergence analysis of Primal–Dual splitting methods

In this paper, we study the local linear convergence properties of a versatile class of Primal–Dual splitting methods for minimizing composite non-smooth convex optimization problems. Under the assumption that the non-smooth components of the problem are partly smooth relative to smooth manifolds, we present a unified local convergence analysis framework for these methods. More precisely, in our framework, we first show that (i) the sequences generated by Primal–Dual splitting methods identify a pair of primal and dual smooth manifolds in a finite number of iterations, and then (ii) enter a local linear convergence regime, which is characterized based on the structure of the underlying active smooth manifolds. We also show how our results for Primal–Dual splitting can be specialized to cover existing ones on Forward–Backward splitting and Douglas–Rachford splitting/ADMM (alternating direction methods of multipliers). Moreover, based on these obtained local convergence analysis result, several practical acceleration techniques are discussed. To exemplify the usefulness of the obtained result, we consider several concrete numerical experiments arising from fields including signal/image processing, inverse problems and machine learning. The demonstration not only verifies the local linear convergence behaviour of Primal–Dual splitting methods, but also the insights on how to accelerate them in practice.     

Weighted estimates for the multilinear maximal function on the upper half‐spaces

For a general dyadic grid, we give a Calderón–Zygmund type decomposition, which is the principle fact about the multilinear maximal function on the upper half‐spaces. Using the decomposition, we study the boundedness of . We obtain a natural extension to the multilinear setting of Muckenhoupt's weak‐type characterization. We also partially obtain characterizations of Muckenhoupt's strong‐type inequalities with one weight. Assuming the reverse Hölder's condition, we get a multilinear analogue of Sawyer's two weight theorem. Moreover, we also get Hytönen–Pérez type weighted estimates.     

Necessary and Sufficient Conditions for Qualitative Properties of Infinite Dimensional Linear Programming Problems

Necessary and sufficient conditions for qualitative properties of infinite dimensional linear programing problems such as solvability, duality, and complementary slackness conditions are studied in this article. As illustrations for the results, we investigate the parametric version of Gale’s example.     

Solvability of a nonlinear fifth‐order difference equation

Some formulas for well‐defined solutions to four very special cases of a nonlinear fifth‐order difference equation have been presented recently in this journal, where some of them were proved by the method of induction, some are only quoted, and no any theory behind the formulas was given. Here, we show in an elegant constructive way how the general solution to the difference equation can be obtained, from which the special cases very easily follow, which is also demonstrated here. We also give some comments on the local stability results on the special cases of the nonlinear fifth‐order difference equation previously publish in this journal.